package MAIN;

import sun.dc.pr.PRError;
import sun.reflect.generics.tree.Tree;

import javax.swing.*;
import java.io.PrintWriter;
import java.util.*;
import java.util.List;

class A {
    int i;
    static  String s;
    void method() {}
    static void method2() {}
}
class B extends A {

}
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
class TreeNode1 {
    public TreeNode1 left;
    public TreeNode1 right;
    public int val;
    public TreeNode1(int val) {
        this.val = val;
    }
}

class Test {
    public static void main22(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node = new ListNode(1);
        //ListNode node1 = new ListNode(3);
        head.next = node;
        //node.next = node1;
        // 删除链表中的重复节点
        //deleteDuplication(head);

        // 删除链表中的节点
        //ListNode res = deleteNode(head, 1);

        // 从尾到头打印链表
//        ArrayList<Integer> arr = printListFromTailToHead(head);
//        for (int i = 0; i < arr.size(); i++) {
//            System.out.println(arr.get(i));
//        }

        // 测试三数之和
//        int[] arr = {-2, 0, 0, 2, 2};
//        ArrayList<ArrayList<Integer>> res = threeSum(arr);
//        for (ArrayList<Integer> arrayList : res) {
//            System.out.println(arrayList);
//        }

        // 测试数组中只出现一次的数字
//        int[] ret = {1,1,1,1,4,6};
//        int[] res = FindNumsAppearOnce(ret);
//        for (int i = 0; i < res.length; i++) {
//            System.out.print(res[i] + " ");
//        }
    }

    // 输出二叉树的右视图
    public int[] solve(int[] preOrder, int[] inOrder) {
        TreeNode1 root = reConstructBinaryTree(preOrder, inOrder);
        Queue<TreeNode1> queue = new LinkedList<>();
        queue.offer(root);
        int k = 0;
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode1 cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                if (i == size - 1) list.add(cur.val);
            }
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    // 重建二叉树
    public TreeNode1 reConstructBinaryTree(int [] pre, int [] vin) {
        return rebuildChild(pre, vin, 0, vin.length - 1);
    }
    public int k = 0;
    public TreeNode1 rebuildChild(int[] pre, int[] vin, int begin, int end) {
        // 终止条件
        if (begin > end) return null;
        TreeNode1 root = new TreeNode1(pre[k]);
        int rootIndex = findIndex(vin, begin, end, pre[k]);
        k++;
        root.left = rebuildChild(pre, vin, begin, rootIndex - 1);
        root.right = rebuildChild(pre, vin, rootIndex + 1, end);
        return root;
    }
    private int findIndex(int[] vin, int begin, int end, int val) {
        for (int i = begin; i <= end; i++) {
            if (vin[i] == val) return i;
        }
        return -1;
    }

    // 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.value : 0;
            int n2 = l2 != null ? l2.value : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry > 0) tail.next = new ListNode(carry);
        return head;
    }

    public ListNode reverse(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        head.next = null;
        ListNode cur = head.next;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    // 前k个高频单词
    public List<String> topKFrequent(String[] words, int k) {

        // 1. 遍历数组，统计每个单词出现的频率
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            if (!map.containsKey(words[i])) map.put(words[i], 1);
            else map.put(words[i], map.get(words[i]) + 1);
        }
        // 2. 建立小根堆 并重写比较规则
        PriorityQueue<Map.Entry<String, Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                // 如果频率相等就按照字母的字典序进行比较
                if (o1.getValue().compareTo((o2.getValue())) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                // 如果频率不等就按照出现次数的字典序进行比较
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        // 3. 遍历 hashMap，将其中的数据放到小根堆
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String, Integer> top = minHeap.peek();
                if (top.getValue() < entry.getValue()) {
                    minHeap.poll();
                    minHeap.offer(entry);
                } else {
                    // 频率相同
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }
        // 4. 此时小根堆中已经有结果了,但是还需要由高到低进行排序
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            ret.add(key);
        }
        Collections.reverse(ret);
        return ret;
    }

    // 坏键盘打字
    public static void main122(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (scan.hasNextLine()) { // 注意 while 处理多个 case
            String s1 = scan.nextLine();
            String s2 = scan.nextLine();
            fun(s1, s2);
        }
    }
    public static void fun(String s1, String s2) {
        Set<Character> set = new HashSet<>();
        for (char ch : s2.toUpperCase().toCharArray()) {
            set.add(ch);
        }
        Set<Character> setBroken = new HashSet<>();
        for (char ch : s1.toUpperCase().toCharArray()) {
            if (!set.contains(ch) && !setBroken.contains(ch)) {
                setBroken.add(ch);
                System.out.print(ch);
            }
        }

    }

    // 字符串的排列
    public void recursion(ArrayList<String> res, char[] str, StringBuffer temp,
                          boolean[] vis) {
        if (temp.length() == str.length) {
            res.add(new String(temp));
            return;
        }
        for (int i = 0; i < str.length; i++) {
            if (vis[i]) continue;
            if (i > 0 && str[i - 1] == str[i] && !vis[i - 1]) continue;
            vis[i] = true;
            temp.append(str[i]);
            recursion(res, str, temp, vis);
            // 回溯
            vis[i] = false;
            temp.deleteCharAt(temp.length() - 1);
        }
    }
    public ArrayList<String> Permutation (String str) {
        ArrayList<String> res = new ArrayList<>();
        if (str == "" || str.length() == 0) return res;
        char[] charStr = str.toCharArray();
        Arrays.sort(charStr);
        boolean[] vis = new boolean[str.length()];
        Arrays.fill(vis, false);
        StringBuffer temp = new StringBuffer();
        recursion(res, charStr, temp, vis);
        return res;
    }

    //有重复项数字的全排列
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        return null;
    }

    // 序列化二叉树
    public int index = 0;
    private void SerializeFun(TreeNode root, StringBuilder str) {
        if (root == null) {
            str.append('#');
            return;
        }
        str.append(root.value).append('!');
        SerializeFun(root.left, str);
        SerializeFun(root.right, str);
    }
    // 处理序列化
    String Serialize(TreeNode root) {
        if (root == null) return "#";
        StringBuilder res = new StringBuilder();
        SerializeFun(root, res);
        return res.toString();
    }
    private TreeNode DeserializeFun(String str) {
        if (str.charAt(index) == '#') {
            index++;
            return null;
        }
        int val = 0;
        while (str.charAt(index) != '!' && index != str.length()) {
            val = val * 10 + ((str.charAt(index)) - '0');
            index++;
        }
//        TreeNode root = new TreeNode(val);
//        if (index == str.length()) return root;
//        else index++;
//        root.left = DeserializeFun(str);
//        root.right = DeserializeFun(str);
//        return root;
        return null;
    }
    // 处理反序列化
    TreeNode Deserialize(String str) {
        if (str == "#") return null;
        TreeNode res = DeserializeFun(str);
        return res;
    }

    // 二叉搜索树与双向链表
    public TreeNode head = null;
    public TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) return null;
        Convert(pRootOfTree.left);
        if (pre == null) {
            head = pRootOfTree;
            pre = pRootOfTree;
        } else {
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }

    //宝石和石头
    public int numJewelsInStones(String jewels, String stones) {
        char[] jew = jewels.toCharArray();
        char[] sto = stones.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < jew.length; i++) {
            map.put(jew[i], 1);
        }
        int count  = 0;
        for (int i = 0; i < sto.length; i++) {
            if (map.containsKey(sto[i])) count++;
        }
        return count;
    }

    // 复杂链表的复制
    public RandomListNode Clone(RandomListNode head) {
        if (head == null) return head;
        RandomListNode res = new RandomListNode(-1);
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        RandomListNode pre = res;
        while (cur != null) {
            RandomListNode clone = new RandomListNode(cur.label);
            map.put(cur, clone);
            pre.next = clone;
            pre = pre.next;
            cur = cur.next;
        }
        for (HashMap.Entry<RandomListNode, RandomListNode> entry : map.entrySet()) {
            if (entry.getKey().random == null)
                entry.getValue().random = null;
            else
                entry.getValue().random = map.get(entry.getKey().random);
        }
        return res.next;
    }

    //二叉树中和为某一值的路径(一)
    public boolean hasPathSum (TreeNode root, int sum) {
        if (root == null) return false;
        if (root.left == null && root.right == null && sum - root.value == 0)
            return true;
        return hasPathSum(root.left, sum-root.value) ||
                hasPathSum(root.right, sum-root.value);
    }

    //二叉树中和为某一值的路径(二)
    private ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    private ArrayList<Integer> path = new ArrayList<>();
    void dfs(TreeNode root, int sum) {
        if (root == null) return;
        path.add(root.value);
        sum -= root.value;
        if (root.left == null && root.right == null && sum == 0)
            res.add(new ArrayList<>(path));
        dfs(root.left, sum);
        dfs(root.right, sum);
        path.remove(path.size() - 1);
    }
    public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
        dfs(root, target);
        return res;
    }

    // 二叉搜索树的后序遍历序列
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0) return false;
        return order(sequence, 0, sequence.length - 1);
    }

    private boolean order(int[] sequence, int left, int right) {
        if (left >= right) return true;
        int j;
        int mid = sequence[right];
        // 找到左子树和右子树的分界点，j 就是左子树的最后一个节点的下标
        for (j = right; j >= left; j--) {
            int cur = sequence[j];
            if (cur < mid) break;
        }
        // 判断左子树是否合法
        for (int i = j; i >= left; i--) {
            int cur = sequence[i];
            if (cur > mid) return false;
        }
        // 左子树和右子树都得合法
        return order(sequence, left, j) && order(sequence, j + 1, right - 1);
    }

    //从上往下打印二叉树
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            list.add(cur.value);
            if (cur.left != null) queue.offer(cur.left);
            if (cur.right != null) queue.offer(cur.right);
        }
        return list;
    }

    //左旋转字符串
    public String LeftRotateString2(String str, int n) {
        if (str.length() == 0) return "";
        char[] s = str.toCharArray();
        int m = s.length;
        n = n % m;
        reverse2(s, 0, m - 1);
        reverse2(s, 0, m - 1 - n);
        reverse2(s, m - n, m - 1);
        return new String(s);
    }
    private char[] reverse2(char[] s, int start, int end) {
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            start++;
            end--;
        }
        return s;
    }

    public static void main33(String[] args) {
//        int[] arr = {1,2,4,7,11,15};
//        int sum = 15;
//        ArrayList<Integer> list = FindNumbersWithSum(arr, sum);
//        for (int i = 0; i < list.size(); i++) {
//            System.out.print(list.get(i) + " ");
//        }
        // 测试活动窗口最大值
        int[] arr = {10,14,12,11};
        int size = 1;
        ArrayList<Integer> list = maxInWindows(arr, size);
        System.out.println("===============");
    }

    // 数组中只出现一次的两个数字
    public int[] FindNumsAppearOnce1(int[] nums) {
        int[] res = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                int val = map.get(nums[i]);
                map.put(nums[i], val + 1);
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) == 1) {
                res[i] = nums[i];
            }
            if (i == 2) break;
        }
        Arrays.sort(res);
        return res;
    }

    // 二叉树的深度
    public int treeHeight(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = treeHeight(root.left);
        int rightDepth = treeHeight(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }

    // 二叉搜索树的第k个节点
    // 记录返回的节点
    private TreeNode result = null;
    private int count = 0;
    public void inorder(TreeNode root, int k) {
        // 中序遍历二叉树，一直遍历到第k个节点即可，count技术是否到 k
        // res指向的是第 k 个节点
        if (root == null || count > k) return;
        inorder(root.left, k);
        count++;
        if (count == k) result = root;
        inorder(root.right, k);
    }
    public int KthNode (TreeNode root, int k) {
        inorder(root, k);
        if (res != null) return result.value;
        else return -1;
    }

    // 买股票的最佳时机(含冷冻期)
    public int maxProfit(int[] prices) {
        // 创建 dp表
        // 初始化
        // 填表
        // 返回值
        int len = prices.length;
        int[][] dp = new int[len][3];
        dp[0][0] = -prices[0];
        for(int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][2]);
            dp[i][2] = dp[i-1][0] + prices[i];
        }
        return Math.max(dp[len-1][1], dp[len-1][2]);
    }



    //孩子们的游戏（圆圈中最后剩下的数）
    public int LastRemaining_Solution (int n, int m) {
        return 0;
    }

    //扑克牌顺子
    public boolean IsContinuous (int[] numbers) {
        // 创建一个hashMap
        HashMap<Integer, Integer> map = new HashMap<>();
        // 使用两个变量记录这手牌的上下界
        int max = 0;
        int min = 13;
        // 遍历每一张牌， 0牌可以重读，非0牌重读则不能为顺子，用哈希表检查去重
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] > 0) {
                // 顺子不能重复
                if (map.containsKey(numbers[i])) {
                    return false;
                } else {
                    //将新牌加入到哈希表中
                    map.put(numbers[i], i);
                    if (numbers[i] >= max) max = numbers[i];
                    if (numbers[i] <= min) min = numbers[i];
                }
            }
        }
        //如果两张牌之差 >= 5 剩下的三张牌一定补不齐
        if ((max - min) >= 5) return false;
        else return true;
    }

    // 滑动窗口的最大值
    public static ArrayList<Integer> maxInWindows(int[] num, int size) {
        return null;
    }


    // 左旋转字符串
    public String LeftRotateString (String str, int n) {
        if (str.isEmpty() || str.length() == 0) return "";
        int m = str.length();
        n = n % m;
        // 逆置全部字符串
        char[] s = str.toCharArray();
        reverse(s, 0, m - 1);
        reverse(s, 0, m - 1 - n);
        reverse(s, m - n, m - 1);
        return new String(s);
    }

    private void reverse(char[] s, int start, int end) {
        while (start < end) swap(s, start++, end--);
    }

    private void swap(char[] s, int a, int b) {
        char temp = s[a];
        s[a] = s[b];
        s[b] = temp;
    }

    // 和为 sum 的两个数字
    public static ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        Arrays.sort(array);
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            if (array[left] + array[right] == sum) {
                list.add(array[left]);
                list.add(array[right]);
                break;
            } else if (array[left] + array[right] > sum) {
                right--;
            } else {
                left++;
            }
        }
        return list;
    }

    // 二叉树的深度
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = TreeDepth(root.left);
        int rightDepth = TreeDepth(root.right);
        int maxDepth = leftDepth < rightDepth ? rightDepth : leftDepth;
        return maxDepth + 1;
    }

    // 删除链表中重复的节点
    public static ListNode deleteDuplication(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode cur = pre;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.value == cur.next.next.value) {
                int tmp = cur.next.value;
                while (cur.next != null && tmp == cur.next.value) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return pre.next;
    }

    // 删除一个链表中的节点
    public static ListNode deleteNode (ListNode head, int val) {
        if (head == null) return null;
        if (head.value == val) {
            head = head.next;
            return head;
        }
        ListNode cur = head;
        ListNode pre = new ListNode(-1);
        pre.next = head;
        while (cur != null) {
            if (cur.value == val) break;
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        return head;
    }

    //从尾到头打印链表
    public static ArrayList<Integer> printListFromTailToHead(ListNode head) {
        ArrayList<Integer> res = new ArrayList<>();
        if (head == null) return res;
        ListNode cur = head.next;
        head.next = null;
        while (cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        cur = head;
        while (cur != null) {
            res.add(cur.value);
            cur = cur.next;
        }
        return res;
    }

    // 交换位置函数
    private void swap(ArrayList<Integer> num, int i1, int i2) {
        int temp = num.get(i1);
        num.set(i1, num.get(i2));
        num.set(i2, num.get(i1));
    }
    public void recursion(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> num, int index) {
        // 分支进入结尾，找到一种排列
        if (index == num.size() - 1) res.add(num);
        else {
            for (int i = index; i < num.size(); i++) {
                swap(num, i, index);
                recursion(res, num, index+1);
                swap(num, i, index);
            }
        }
    }
    // 没有重复项数字的全排列
    public ArrayList<ArrayList<Integer>> permute (int[] num) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> nums = new ArrayList<>();
        // 数组转 ArrayList
        for (int i = 0; i < num.length; i++) {
            nums.add(num[i]);
        }
        recursion(res, nums, 0);
        return res;
    }

    // 三数之和
    public static ArrayList<ArrayList<Integer>> threeSum (int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int n = num.length;
        if (n < 3) return res;
        Arrays.sort(num);
        for (int i = 0; i < n - 2; i++) {
            if (i != 0 && num[i] == num[i-1]) continue;
            int left = i + 1;
            int right = n - 1;
            int target = -num[i];
            while (left < right) {
                if (num[left]  + num[right] == target) {
                    ArrayList<Integer> temp = new ArrayList<>();
                    temp.add(num[i]);
                    temp.add(num[left]);
                    temp.add(num[right]);
                    res.add(temp);
                    while (left + 1 < right && num[left] == num[left + 1]) left++;
                    while (right - 1 > left && num[right] == num[right - 1]) right--;
                    left++;
                    right--;
                } else if (num[left] + num[right] < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return res;
    }

    // 缺失的第一个整数
    public int minNumberDisappeared (int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], 1);
        }
        int res = 1;
        while (map.containsKey(res)) {
            res++;
        }
        return res;
    }

    //数组中只出现一次的两个数字
    public static int[] FindNumsAppearOnce (int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) == null) {
                map.put(nums[i], 1);
            } else {
                int value = map.get(nums[i]);
                map.put(nums[i], value + 1);
            }
        }
        int[] arr = new int[2];
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) == 1) {
                arr[j] = nums[i];
                j++;
            }
            if (j == 2) break;
        }
        Arrays.sort(arr);
        return arr;
    }


    //两数之和2
    public int[] twoSum2 (int[] numbers, int target) {
        int[] res = new int[0];
        //1.创建一个哈希表
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //在表中查找  目标值-numbers[i]
        for (int i = 0; i < numbers.length; i++) {
            int tmp = target - numbers[i];
            //如果没有找到，就把数组中的这个值加入哈希表中
            if (!hashMap.containsKey(tmp)) {
                hashMap.put(numbers[i], i);
            }else {
                return new int[] {hashMap.get(numbers[i]) + 1, i + 1};
            }
        }
        return res;
    }
    //两数之和  时间复杂度：O(N^2)
    public int[] twoSum (int[] numbers, int target) {
        int n = numbers.length;
        int[] res = {-1, -1};
        //遍历数组
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;
    }
    //连续子数组的最大和  ”一定是要连续的“
    public int FindGreatestSumOfSubArray (int[] array) {
        //1.创建dp表
        int[] dp = new int[array.length + 1];
        //2.初始化  初始化数组的时候自动就是0，可以不写
        //dp[0] = 0;
        //3.填表
        int ret = Integer.MIN_VALUE;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Math.max(array[i-1], dp[i-1] + array[i-1]);
            if (dp[i] > ret) ret = dp[i];
        }
        //注意：此时不是返回dp数组的最后一个，而是最大值
        return ret;
    }

    //表达式求值
    public int solve2 (String s) {
        return -1;
    }
    //首先将中缀表达式转化成后缀表达式
    public static void main11(String[] args) {
        //定义一个逆波兰表达式
        String express = "3 4 + 5 * 6 - ";
        //将逆波兰表达式转为一个list数组
        List<String> stringList = Arrays.asList(express.split(" "));
        //int result = calculate(stringList);
        //System.out.println(result);
    }

    //寻找第K大
    //找前k个最小的数，就建立一个大根堆，找前k个最大的数，就建立一个小根堆
    public static int findKth (int[] arr, int n, int K) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(K);
        for (int i = 0; i < arr.length; i++) {
            if (i < K) {
                minHeap.offer(arr[i]);//入堆
            }else {
                int val = arr[i];
                if (val > minHeap.peek()) {
                    minHeap.poll();
                    minHeap.offer(arr[i]);
                }
            }
        }
        return minHeap.peek();
    }

    public static void main6(String[] args) {
        int[] arr = {1,3,5,2,2};
        int a = findKth(arr,5,3);
        System.out.println(a);
    }
    //把数字翻译成字符串
    public int solve (String nums) {
        //创建dp表
        int n = nums.length();
        int[] dp = new int[n];
        char[] s = nums.toCharArray();
        if (s[0] != '0') dp[0] = 1;
        if (n == 1) return dp[0];
        if (s[0] != '0' && s[1] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + s[1] - '0';
        if (t >= 10 && t <= 26) dp[1] += 1;
        //填表
        for (int i = 2; i < n; i++) {
            if (s[i] != '0') dp[i] += dp[i-1];

            int tt = (s[i-1]-'0') * 10 + s[i] -'0';
            if (tt >= 10 && tt <= 26) dp[i] += dp[i-2];
        }
        return dp[n-1];
    }

    //矩阵最小路径和
    public int minPathSum2 (int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }
        dp[0][1] = dp[1][0] = 0;
        //填表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1])
                        + matrix[i-1][j-1];
            }
        }
        return dp[m][n];
    }
    //不同路径的数目
    public int uniquePaths2 (int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        //填表
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }


    //最长公共子序列（只要有相同的字符就输出）
    public static void LCS (String s1, String s2) {
        Set<Character> set = new HashSet<>();
        //StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s1.length(); i++) {
            char ch = s1.charAt(i);
            set.add(ch);
        }
        for (int i = 0; i < s2.length(); i++) {
            char ch = s2.charAt(i);
            if (set.contains(ch)) {
                System.out.print(ch + " ");
            }
        }

    }

    public static void main5(String[] args) {
        String s1 = "1A2C3D4B56";
        String s2 = "B1D23A456A";
        LCS(s1, s2);
    }
    //最小的K个数
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        return null;
    }

    //输出二叉树的右视图
    //首先根据前序遍历和中序遍历构建二叉树 ，然后按深度优先遍历搜索遍历树
    /*public int[] solve (int[] preOrder, int[] inOrder) {
        TreeNode root = buildTree(preOrder, inOrder);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int k = 0;
        List<Integer> list = new ArrayList<>();
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                TreeNode cur = queue.poll();
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
                //如果出队列出到了当前层的最后一个节点，此时就把结果添加进去
                if (j == size - 1) {
                    list.add(cur.value);
                }
            }
        }
        int[] arr = new int[list.size()];
        for (int j = 0; j < list.size(); j++) {
            arr[j] = list.get(j);
        }
        return arr;
    }
    public TreeNode buildTree(int[] preOrder, int[] inOrder) {
        return buildTreeChild(preOrder, inOrder, 0, inOrder.length - 1);
    }
    public int i = 0;
    public TreeNode buildTreeChild(int[] preOrder, int[] inOrder, int begin, int end) {
        if (begin > end) return null;
        TreeNode root = new TreeNode(preOrder[i]);
        int rootIndex = findIndex(inOrder, begin, end, preOrder[i]);
        i++;
        root.left = buildTreeChild(preOrder, inOrder, begin, rootIndex - 1);
        root.right = buildTreeChild(preOrder, inOrder, rootIndex + 1, end);
        return root;
    }

    private int findIndex(int[] inOrder, int begin, int end, int key) {
        for (int j = begin; j <= end; j++) {
            if (inOrder[j] == key) return j;
        }
        return -1;
    }*/

    //地下城游戏
    public int calculateMinimumHP(int[][] d) {
        //1.创建一个dp表  2.初始化  3.填表   4.返回值
        int m = d.length, n = d[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int j = 0; j <= n; j++) dp[m][j] = Integer.MAX_VALUE;
        for (int i = 0; i <= m; i++) dp[i][n] = Integer.MAX_VALUE;
        dp[m][n-1] = dp[m-1][n] = 1;
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i][j+1], dp[i+1][j]) - d[i][j];
                dp[i][j] = Math.max(1, dp[i][j]);
            }
        }
        return dp[0][0];
    }
    //最小路径和
    public int minPathSum(int[][] grid) {
        //状态表示：dp[i][j]表示从起点到达[i][j]位置时，最小路径和
        //状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + g[i][j]
        //初始化：加上一行一列，之后初始化成最大值,但是要注意：此时不全都是最大值。
        //最开始的位置只能是从起点开始走，没有选择，dp方程是那个，所以此时只有初始化成0
        //此时才不会影响填表的正确性。    2. 注意下标的映射
        //填表顺序：从上往下，每一行从左往右     返回值：dp[m][n]
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for (int i = 0; i <= n; i++) {
            dp[0][i] =Integer.MAX_VALUE;
        }
        dp[0][1] = dp[1][0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }

    //下降路径最小和
    public int minFallingPathSum(int[][] matrix) {
        //状态表示:dp[i][j]表示到达[i][j]位置时最小的下降路径
        //状态方程     // 初始化：1.里边的值要保证后面填表是正确的
        // 2. 下标的映射：加上一行，加上两列，所有位置初始化成最大值，然后第一行改成0
        //填表顺序：从上往下，   返回值: 最后一行dp表中的最小值
        int n = matrix.length;
        int[][] dp = new int[n + 1][n + 2];
        for (int i = 1; i <= n; i++) {
            dp[i][0] = dp[i][n+1] = Integer.MAX_VALUE;
        }
        //填表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int a = Math.min(dp[i-1][j-1],dp[i-1][j]);
                //此时一定要注意下标的映射
                dp[i][j] = Math.min(a,dp[i-1][j+1]) + matrix[i - 1][j - 1];
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            min = Math.min(min,dp[n][i]);
        }
        return min;
    }
    //礼物最大值
    public int maxValue(int[][] grid) {
        //dp[i][j]表示，到达[i，j]位置的时候，此时的最大价值
        //状态转移方程：dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + g[i][j]
        //初始化：多加一行和一列，因为每个格子都要依赖上一个和前一个的格子来初始化
        //1.创建dp表
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                //此处填表一定要注意：多给了一行和一列，此时在加原来的grid表时，
                //一定要把这一行和一列减去
                dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }

    //不同路径II（在路径中有障碍物）
    //状态方程：dp[i][j] = 0(有障碍物) || dp[i-1][j] + dp[i][j-1]
    //如果[i-1][j]或者[i][j-1] 有障碍物也没关系，此时如果一个格子中有障碍物时，dp[][] = 0;
    /*所以0 + 0 到[i][j]的总方案数还是0*/
    /*3.初始化：还是多加一行和一列（这个二维数组中的元素代表的是方案数，所以只要保证[0][0]这个格子
    是正确的即可），所以才能保证填表的顺序是正确的     4.注意下标的映射关系，此时给的是一个矩阵
    开始的时候多加了一行和一列，所以下标统一向右下角移动一位，所以要根据dp表找回矩阵的位置就需要
    下标都-1.*/
    /*返回值：dp[m][n]*/
    public int uniquePathsWithObstacles(int[][] ob) {
        int m = ob.length, n = ob[0].length;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;//初始化
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                //因为dp表的初始化开始存放的元素就是0，所以只需要看没有障碍物的情况即可
                if (ob[i - 1][j - 1] == 0) dp[i][j] = dp[i-1][j] + dp[i][j-1];
                //注意：ob是原始的矩阵，新的dp表在ob的基础上加了一行和一列，答案需要
                //返回的是原始的ob矩阵的mn格子有多少种方案数，所以下标统一往左上角挪动一个
                //
            }
        }
        return dp[m][n];
    }

    //不同路径I
    //状态表示：以[i,j]位置为结尾时，，，，
    //dp[i][j]表示：走到i，j位置时，一共有多少种不同的路径
    //状态转移方程：最近的一步来划分问题 --> dp[i][j] = dp[i-1][j] + dp[i][j-1]
    //然后是初始化，找到会越界的行和列，所以此时需要增加一行和一列(虚拟节点)，
    //1.而且虚拟节点中的值要可以保证后面填表的结果是正确的
    //2. 下标的映射     最后填表的顺序是从上往下，从左往右
    //返回值：dp[m][n]
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
    //解码方法
    //dp[i]表示以i位置为结尾时，解码方法的总数
    public int numDecodings1(String ss) {
        //1.创建一个dp表
        //2.初始化去处理边界
        //3.填表    4.确定返回值
        char[] s = ss.toCharArray();
        int n = ss.length();
        int[] dp = new int[n];
        //初始化第一个位置
        if (s[0] != '0') dp[0] = 1;
        if (n == 1) return dp[0];

        //初始化第二个位置
        if (s[1] != '0' && s[0] != '0') dp[1] += 1;
        int t = (s[0] - '0') * 10 + (s[1] - '0');
        if (t >= 10 && t <= 26) dp[1] += 1;

        //填表
        for (int i = 2; i < n; i++) {
            //先处理第一种情况
            if (s[i] != '0') dp[i] += dp[i-1];
            //处理第二种情况
            int tt = (s[i - 1] - '0') * 10 + (s[i] - '0');
            if (tt >= 10 && tt <= 26) dp[i] += dp[i-2];
        }
        return dp[n-1];
    }
    //解码方法总数：优化后的代码
    public int numDecodings(String ss) {
        char[] s = ss.toCharArray();
        int n = ss.length();
        //首先是多开一个位置，把存放s字符的数组整体往后挪动一个位置
        int[] dp = new int[n+1];
        dp[0] = 1;//保证后续的填表是正确的
        if (s[1-1] != '0') dp[1] = 1;
        //填表
        for (int i = 2; i <= n; i++) {
            //先处理第一种情况
            if (s[i-1] != '0') dp[i] += dp[i-1];
            //处理第二种情况
            int tt = (s[i - 2] - '0') * 10 + (s[i-1] - '0');
            if (tt >= 10 && tt <= 26) dp[i] += dp[i-2];
        }
        return dp[n];
    }
    private String name = "abc";
    public static void main1(String[] args) {
        Test test = new Test();
        Test testB = new Test();
        String result = test.equals(testB) + ",";//没有重写equals方法，Object类中的equals比较的还是引用的地址
        result += test.name.equals(testB.name) + ",";//没有new一个对象，是直接赋值，会放进字符串常量池中
        result += test.name == testB.name;//所以比较的是同一个对象
        System.out.println(result);//false;true;true
        /*解析：1.只有重写了equals方法写定比较规则后，才可以是按内容进行比较，否则就调用的是Object类中
        *的equals方法，比较的是对象在内存中的地址，结果就是false。
        * 2.name成员变量并没有被static关键字修饰，所以每个Text类对象被创建时，都会先执行private String name = "abc"；
        * 在对象初始化时，jvm会先检查字符串常量池中是否存在改字符串对象，此时常量池中并不存在"abc"这个对象，jvm先在常量池中
        * 创建这个对象，当textB被创建时，也是先检查常量池中是否有这个对象，如果有，jvm直接返回该字符串在常量池中的地址，而不会
        * 创建新的对象，所以第二个指向的是同一个对象，*/
    }
}
public class NewCoderPractice {
    //表达式求值
    public int solve (String s) {
        return -1;
    }
    //有效括号序列：碰到左括号就入栈，碰到右括号就peek看是否匹配
    //如果匹配就出栈，不匹配返回false，最后看栈是否为空，如果是空的
    //此时就说明括号是匹配的
    public boolean isValid (String s) {
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '[' || ch == '{' || ch == '(') {
                stack.push(ch);
            }else {
                if (stack.isEmpty()) return false;
                char ch2 = stack.peek();
                if (ch2 == '(' && ch == ')' || ch2 == '[' && ch == ']' ||
                ch2 == '{' && ch == '}') {
                    stack.pop();
                }
            }
        }
        if (stack.isEmpty()) return true;
        return false;
    }
    //链表中倒数最后k个节点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int len = 0;
        ListNode cur = pHead;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        if (len < k) return null;

        ListNode fast = pHead;
        ListNode slow = pHead;
        while (k != 1) {
            fast = fast.next;
            k--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    public static void main(String[] args) {

    }
    public static void main7(String[] args) {
        String s1 = "coder";
        String s2 = "coder";
        String s3 = "coder" + s2;
        String s4 = "coder" + "coder";
        String s5 = s1 + s2;
        System.out.println(s3 == s4);//false
        System.out.println(s3 == s5);//false
        System.out.println(s4 == "codercoder");//true
        System.out.println(s5 == "codercoder");//false
        //解析：只要是字符串字面常量直接赋值，此时是放在常量池中的，如果是变量赋值，
    }
    public static void main6(String[] args) {
        String s1 = new String();
        String s2 = new String();
        System.out.println(s1.equals(s2));
    }
    //最小花费爬楼梯：   可以从0或者1号下标开始向上爬
    //注意楼顶的位置是数组最后一个元素的下一个位置
    public int minCostClimbingStairs (int[] cost) {
        //1.状态表示：一般都是整个问题的子问题
        //2.状态转移方程
        //3.初始化处理边界问题
        //4.返回值
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        //填表
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);
        }
        return dp[n];
    }
    //最小花费爬楼梯  解法2
    public int minCostClimbingStairs2 (int[] cost) {
        //dp[i]表示从i位置出发到达楼顶的最小花费
        //楼顶是dp[n],最后走的时候要么是从n-1位置跳到n，要么是从n-2位置跳到n
        //此时就需要初始化最后两个位置即可
        int n = cost.length;
        int[] dp = new int[n];//此时就不用再多开一个位置了
        dp[n-1] = cost[n-1];
        dp[n-2] = cost[n-2];
        for (int i = n-3; i >= 0; i--) {
            dp[i] = Math.min(dp[i+1],dp[i+2]) + cost[i];
        }
        return Math.min(dp[0],dp[1]);
    }

    //跳台阶
    public int jumpFloor(int target) {
        int[] dp = new int[target];
        //初始化
        if (target == 1) return 1;
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 1; i <= target; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[target-1];
    }

    //斐波那契数列：给一个正整数，输出这个正整数是第几项
    public int Fibonacci1(int n) {
        if (n < 3) {
            return 1;
        }else {
            return Fibonacci1(n-1) + Fibonacci1(n-2);
        }

    }
    public int Fibonacci(int n) {
        if (n < 2) {
            return 1;
        }
        int a = 1;
        int b = 1;
        int sum = 0;
        for (int i = 2; i <= n; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }
        return sum;
    }



    private static final String str = "taobao";
    public static void main2(String[] args) {
        String s1 = new String("hello");
        String s2 = new String("hello");
        System.out.println(s1 == s2);
        System.out.println(s1.equals(s2));
        final String s3 = "tao";
        final String s4 = "bao";
        System.out.println((s3+s4) == str);//此时是相等的，编译器已经自动优化了
        //没有new出来的对象都是在栈内存中存放的
        /*float a = 99999999999999999999999999999999999999F;
        long b = 999999999999999999L;*/
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            list.add(i);
        }
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).equals(0)) {
                list.remove(i);
            }
        }
        System.out.println(list.size());
    }
    public static void main1(String[] args) {
        int a = 7;
        do {
            System.out.println(--a);
            --a;
        }while (a != 0);
        System.out.println(a);
    }

    //字符集合
    public static void main3(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextLine()) {
            String str = scan.nextLine();
            String ret = func(str);
            System.out.println(ret);
        }
    }
    private static String func(String str) {
        boolean[] flg = new boolean[124];//默认存放的都是false
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (flg[ch] == false) {
                sb.append(ch);
                flg[ch] = true;
            }
        }
        return sb.toString();
    }

    //合并两个有序的数组: m是A数组的长度，n是B数组的长度
    public void merge(int A[],int m, int B[], int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;//代表A数组的最后一个位置
        //两个数组中都有数据
        //当B的数据放进A数组中时，此时数据是覆盖的
        while (i >= 0 && j >= 0) {
            if (A[i] <= B[j]) {
                A[k--] = B[j--];
            }else {
                A[k--] = A[i--];
            }
        }
        //循环走到这里，上边的while中的条件一定是有一个不满足的
        //有可能A走完了，但是B里边仍然有数据
        while (j >= 0) {
            A[k--] = B[j--];
        }
    }

}
